//
// Created by francklinson on 2021/7/23 AT 0:10.
//
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    bool isCovered(vector<vector<int>> &ranges, int left, int right) {
        // brute force
        bool find = false;
        for (int i = left; i <= right; ++i) {
            find = false;
            for (auto &range : ranges) {
                if (i >= range[0] and i <= range[1]) {
                    find = true;
                    break;
                }
            }
            if (!find) return false;
        }
        return true;
    }

};
class Solution2 { // 差分法
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        vector<int> diff(52, 0);   // 差分数组
        for (auto&& range: ranges){
            ++diff[range[0]];
            --diff[range[1]+1];
        }
        // 前缀和
        int curr = 0;
        for (int i = 1; i <= 50; ++i){
            curr += diff[i];
            if (i >= left && i <= right && curr <= 0){
                return false;
            }
        }
        return true;
    }
};


int main() {
    vector<vector<int>> ranges{{1, 2},
                               {3, 4},
                               {5, 6}};
    Solution solution;
    cout << solution.isCovered(ranges, 2, 5) << endl;
    return 0;
}

